Presentation002
=II - Eager Queue Protocols= List of Presentations Purpose of Presentation Explain How Eager Queue Protocols Work Point of Presentation An Eager Queue Protocol is a Way of Managing a Network of Resources Related Wiki Pages * Eager Queue Protocols Summary Objectives * Manage a network of unreliable servers ** Keep track of available servers ** Allow one server to request the service of another server ** Make the system robust Overview Eager Queue Protocols are a way of managing queues of resources. In the basic protocol there are 6 message types: # JOIN # EXIT # UPDATE # REQUEST # ACCEPT # DECLINE A resource can: * JOIN and EXIT a queue. * UPDATE a queue. * REQUEST services of another resource. * ACCEPT a request from another resource. * DECLINE a request from another resource. The main purpose of the protocol is to determine which resource ACCEPTs a REQUEST, and to make a REQUEST/ACCEPT pair occur as quickly as possible. By predetermining which reource will ACCEPT a REQUEST collisions are avoided. The protocol is called Eager as in the original version a resource that is at the back of the queue will push to the front in the absence of any other messages to let the others know it is still available. This resource will then have priority in ACCEPTing a REQUEST. LKT - Last Known Transmissions In an eager queue the most live available resource will ACCEPT a REQUEST. The liveness of a resource is determined by when it was last heard from. The most recent resource to have communicated is assumed to be the most live. The least recent resource to have communicated is assumed to be the least live. A list of available servers is held by a central server. As each server notifies the central server of its availabilty the central server notes the time of the notification. This data is held in a Last Known Transmission vector. An LKT is an array of Processor Id and Time pairs. Tracking Available Servers Using LKT Slide: No Queuing Processors Slide: Processor 5 JOINs ::* Processor 5 sends a message to the central processor. ::* Processor 5 is now in the Queuing state. Slide: Processor 3 JOINs Slide: Processor 6 JOINs Slide: Processor 2 JOINs Slide: Processor 1 JOINs Slide: Processor 4 JOINs Slide: Processor 5 Sends an UPDATE Making a Request When a request for a server is made the requesting server sends a request to the LKT server. a_{LKT}!GETPID \; . \; a_{LKT}?GETPID(a_{id}) \; . \; a_{id}!REQUEST \; . \; a_{id}?ACCEPT(a_{id}) \; . \; a_{id}!Program \; . \; P_r^1 Slide: Processor 1 EXITs to Start Work Slide: Processor 1 Requests a Processor Id from the Queue Slide: Processor ID 5 is Returned from the Queue Slide: Processor 1 Makes a REQUEST of Processor 5 Slide: Processor 5 ACCEPTs the REQUEST From Processor 1 Slide: Processor 1 Starts a New Process on Processor 5 Slide: Sequence Diagram for Successful Fork Slide: Sequence Diagram for Fork with Failed REQUEST Problems With this Approach * The LKT vector is centralised. * Servers don't know when to send UPDATEs * Too much traffic. Using a Decentralised LKT Slide: Decentralised LKT Slide: TODO Slide: TODO Slide: TODO Slide: TODO Slide: TODO Slide: TODO Slide: TODO Slide: P5 ACCEPTS Immediately * Once a REQUEST is broadcast all processors know who is expected to ACCEPT * P5 ACCEPTs Slide: P5 Fails to ACCEPT - P4 ACCEPTS * All Processors wait for P5 to ACCPET * P5 Fails to ACCEPT * All Processors wait for P4 to ACCPET * P4 ACCEPTS Eager Queues The LKT vector is being used to calculate the most recent processor to broadcast. The actual time intervals are not as important as the order in which processors have been heard. We can simplify the LKT to a list that is similar to a stack when processor Id are added. The difference being that any duplicates further down the list are removed. Slide: Eager Queue Struture : \begin{bmatrix} - \end{bmatrix} P_5 JOINs. : \begin{bmatrix} P_5 \end{bmatrix} P_3 JOINs. : \begin{bmatrix} P_3 & P_5 \end{bmatrix} P_6 JOINs. : \begin{bmatrix} P_6 & P_3 & P_5 \end{bmatrix} P_2 JOINs. : \begin{bmatrix} P_2 & P_6 & P_3 & P_5 \end{bmatrix} P_1 JOINs. : \begin{bmatrix} P_1 & P_2 & P_6 & P_3 & P_5 \end{bmatrix} P_4 JOINs. : \begin{bmatrix} P_4 & P_1 & P_2 & P_6 & P_3 & P_5 \end{bmatrix} P_5 UPDATEs. : \begin{bmatrix} P_5 & P_4 & P_1 & P_2 & P_6 & P_3 \end{bmatrix} Eager Queue Protocols Slide: EQP Version 2 Slide: EQP Version 3 Category:Research